import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution1073 {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        List<Integer> l1=new ArrayList<>();
        for (int i=arr1.length-1;i>=0;i--){
            l1.add(arr1[i]);
        }
        List<Integer> l2=new ArrayList<>();
        for (int i=arr2.length-1;i>=0;i--){
            l2.add(arr2[i]);
        }
        List<Integer> l3=new ArrayList<>();
        for (int i=0;i<Math.min(Math.max(l3.size(),Math.max(l1.size(),l2.size())),10000);i++){
            if (l3.size()==i){
                l3.add(0);
            }
            int p=l1.size()<=i?0:l1.get(i);
            int q=l2.size()<=i?0:l2.get(i);
            l3.set(i,l3.get(i)+p+q);
            if (l3.get(i)>=2){
                if (l3.size()==i+1){
                    l3.add(0);
                }
                if (l3.size()==i+2){
                    l3.add(0);
                }
                l3.set(i+1,l3.get(i+1)+l3.get(i)/2);
                l3.set(i+2,l3.get(i+2)+l3.get(i)/2);
                l3.set(i,l3.get(i)%2);
            }
        }
        int k=l3.size()-1;
        while (l3.size()>1 && l3.get(k)*2==l3.get(k-1)){
            l3.remove(k);
            k--;
            l3.remove(k);
            k--;
        }
        if (l3.size()==0){
            l3.add(0);
        }
        while (l3.size()>1 && l3.get(l3.size()-1)==0){
            l3.remove(l3.size()-1);
        }
        int[] f=new int[l3.size()];
        for (int i=0;i<l3.size();i++){
            f[i]=l3.get(l3.size()-i-1);
        }
        return f;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution1073().addNegabinary(new int[]{1,0,1}, new int[]{1,1,1})));
    }
}
